﻿/*
 * link_next.hpp
 *
 *  Created on: 2020年2月22日
 *      Author: Dylan.Gao
 */

#ifndef _DM_LINK_NEXT_HPP_
#define _DM_LINK_NEXT_HPP_

#include <dm/link_base.hpp>
#include <dm/sparce_color.hpp>

namespace dm{

/**
 * 单向链表，指向下一个
 * 允许形成环
 */
template<typename T>
class TCLinkNext:public TCLinkBase<T>{
public:
	TCLinkNext( const T& p ):TCLinkBase<T>(p),m_next(NULL){
	}

	/**
	 * 将析构本节点开始的链表
	 */
	virtual ~TCLinkNext(){
		if( m_next ){
			TCLinkNext* n = m_next;
			m_next = NULL;	// 确保不会环形
			delete n;
		}
	}

	/**
	 * 是否为环形
	 * @return
	 */
	inline bool isRing()const{
		return getRingNode()!=NULL;
	}

	/**
	 * 获取第一个产生环节点
	 * @return
	 */
	inline const TCLinkNext* getRingNode()const{
		return getRingNode(this);
	}

	/**
	 * 获取第一个产生环节点
	 * @return
	 */
	inline TCLinkNext* getRingNode(){
		return getRingNode(this);
	}

	/**
	 * 以本节点开始的链表节点数量
	 * @return
	 */
	unsigned int size()const{
		TCSparceColor<dm::ptr_t> m;
		unsigned int rt = 0;

		const TCLinkNext<T>* n = this;
		while( n ){
			if( !m.add(dm::ptr_t(n)) )
				return rt;

			n = n->next();
			++rt;
		}

		return rt;
	}

	inline TCLinkNext* next(){
		return m_next;
	}

	inline const TCLinkNext* next()const{
		return m_next;
	}

	bool insert( const T& p ){
		TCLinkNext* n = m_next;
		m_next = new TCLinkNext(p);
		m_next->m_next = n;

		return true;
	}

	/**
	 * 插入操作，不允许插入含有环结构
	 * @param l
	 */
	bool insert( TCLinkNext* l ){
		TCLinkNext* e = l->end();
		if( e==NULL )	// 环形
			return false;

		TCLinkNext* n = m_next;
		m_next = l;
		e->m_next = n;

		return true;
	}

	bool removeNext(){
		if( m_next ){
			TCLinkNext* n = m_next;
			m_next = n->m_next;
			n->m_next = NULL;
			delete n;
			return true;
		}
		return false;
	}

	bool removeNexts(){
		if( m_next ){
			// 注意环形，会导致错误
			TCLinkNext* n = m_next;
			m_next = NULL;
			delete n;
			return true;
		}
		return false;
	}

	TCLinkNext* popNext(){
		TCLinkNext<T>* n = m_next;
		if( n ){
			m_next = n->m_next;
			n->m_next = NULL;
		}

		return n;
	}

	TCLinkNext* popNexts(){
		TCLinkNext<T>* n = m_next;
		if( n )
			m_next = NULL;

		return n;
	}

	TCLinkNext* pushBack( const T& p ){
		TCLinkNext<T>* e = end();
		if( e ){
			e->insert(p);
			return this;
		}

		return NULL;
	}

	TCLinkNext* pushBack( TCLinkNext* l ){
		TCLinkNext<T>* e = end();
		if( e ){
			e->m_next = l;
			return this;
		}

		return NULL;
	}

	TCLinkNext* pushHead( const T& p ){
		TCLinkNext<T>* n = new TCLinkNext<T>(p);
		n->m_next = this;
		return n;
	}

	TCLinkNext* pushHead( TCLinkNext* l ){
		TCLinkNext<T>* n = l->end();
		if( n ){
			n->m_next = this;
			return l;
		}

		return NULL;
	}

	/**
	 * 反序
	 * 支持环
	 * @return
	 */
	TCLinkNext* reverse(){
		TCSparceColor<dm::ptr_t> m;

		TCLinkNext<T>* l = this;
		TCLinkNext<T>* p = l->m_next;
		l->m_next = NULL;

		while( p ){
			if( !m.add(dm::ptr_t(p)) )
				return l;

			TCLinkNext<T>* n = p->m_next;
			p->m_next = l;
			l = p;
			p = n;
		}

		return l;
	}

	inline TCLinkNext* end(){
		return end(this);
	}

	inline const TCLinkNext* end()const{
		return end(this);
	}
protected:
	template<typename TList>
	TList getRingNode( TList n )const{
		TCSparceColor<ptr_t> m;

		while( n ){
			if( !m.add(dm::ptr_t(n)) )
				return n;

			n = n->next();
		}

		return NULL;
	}

	/**
	 * 查找结尾元素
	 * 环不存在结尾元素
	 * @return
	 */
	template<typename TList>
	TList end( TList n )const{
		TCSparceColor<dm::ptr_t> m;
		while( n->m_next ){
			if( !m.add( dm::ptr_t(n)) )
				return NULL;

			n = n->next();
		}

		return n;
	}
private:
	TCLinkNext<T>* m_next;
};

}

#endif /* INCLUDE_DM_LINK_NEXT_HPP_ */
